In entry of text by use of a standard typewriter form of keyboard each key stroke represents a single letter on a non-ambiguous basis. For many applications it is desirable to be able to enter text by use of a readily available telephone having a standard telephone keypad. For example, such text entry would enable an untrained caller to communicate with a hearing-impaired person from any available telephone. However, telephone keypads are overloaded with three letters to a single key which creates ambiguities as to which letter is intended by a single key stroke. Prior approaches toward resolving the ambiguities have typically required two or more key strokes for entry of each letter. Resulting text entry routines have been cumbersome, slow and frustrating to use.
The marriage of computing and telecommunications has spawned an amazing variety of new services and capabilities. Many individuals are currently excluded from participation because they do not have ready access to an alphanumeric terminal and modem. However, most homes in many countries already contain a simple on-line terminal in the form of a telephone. Anyone who has ever placed a telephone call is familiar with the fact that the 2-9 keys of a standard phone dial are each labeled with three letters of the alphabet (the letters Q and Z do not appear). These labels have been used to provide mnemonics to aid in memorizing phone numbers (such as 1-800-FLOWERS) and in modern messaging systems for entering single word strings (such as a database of employee names in a company switchboard application). However, the overloading of three letters on a single key creates a potential ambiguity as to which character was intended.
Resolution of this overloading ambiguity is necessary for unambiguous text entry. For applications involving a small, predetermined vocabulary (such as the switchboard application noted above), a simple hashing scheme will suffice. However the problem becomes considerably more difficult if arbitrary text is to be entered (i.e., text entry free of predetermined constraints on word usage).
A variety of different text entry conventions have been proposed for use with telephone keypad to resolve or reduce ambiguities resulting from the multi-letter keys. Without attempting to address all prior techniques, it can be noted that numerous prior approaches have addressed ambiguity on a letter level. For example, "L" is the third character on the number 5 key and an unambiguous entry can be made by pressing the 5 key three times, followed by pressing the O key to indicate completion of entry of the third letter on the 5 key. Alternatively, L can be entered by pressing the 5 key followed by another key predesignated to indicate the third letter on the 5 key. In each case the letter L is unambiguously entered, but a multi-stroke procedure must be learned and then carried out for each letter.
Other approaches have addressed ambiguity resolution at a word level. Typically, if three keys are activated to represent a three letter word, for example, a dictionary type word list can be accessed to identify all English words formable by the permutations of the three letters represented in each of the three successive letter positions. One approach is to limit word possibilities to a restricted list of words, names or locations so that it is predetermined that only one word can be represented by that specific three key sequence. A word level approach is discussed in the article, "Let Your Fingers Do the Spelling: Disambiguating Words Spelled With the Telephone Keypad", J. R. Davis, AVIOS Journal, 9:57-66, March 1991. Unambiguous operation with a limited word list of streets, words or people is discussed. This article specifically acknowledges the absence of any capability to go beyond a word level operation constrained by a predefined limited word list, concluding that: "Implicit disambiguation does not appear feasible for entering unrestricted English text".
A word level approach which permits less restricted text entry is described in U.S. Pat. No. 4,650,927, issued Mar. 17, 1987. This patent recognizes the basic inability to choose the correct word when the text entry via a telephone keypad results in a list of two or more word possibilities for a particular word position. Instead of reducing word ambiguity by limiting the list of acceptable words, this patent presents the list of possible words to the human recipient of a message. Users presented with such word choices must then use their own judgment in selecting the word which makes the most sense to them in the sequential context presented to them.
Basic shortcomings of all known prior approaches are that they have been either slow and cumbersome if operating on a letter level of ambiguity resolution, or limited in overall capability and performance if operating on a word level of ambiguity resolution. No known prior approach has provided a practical capability of ambiguity resolution on a sentence level utilizing syntax relationships regarding usage of words in a selected language.
Objects of the present invention are, therefore, to provide new and improved sentence reconstruction methods and systems having one or more of the following capabilities:
resolution of word ambiguities based on syntax relationships regarding word usage; PA0 unrestricted text entry via a telephone keypad; PA0 word ambiguity resolution based upon probabilities of word usage and probabilities of one or both of particular word sequences and positioning of words of particular word categories; and PA0 simple text entry protocol. PA0 (a) storing a sentence structure having a sequence of word positions with at least one word position represented by a word group including alternative word choices; PA0 (b) utilizing a stored word use rule set representative of relative frequency of particular word usage in the selected language to derive, for the word group for one of the word positions, probability values for word choices for that word position; PA0 (c) utilizing a stored language rule set representative of usage in the selected language to derive probability values for sequencing of individual word choices for the word position relative to at least one word choice for an adjacent word position in the sentence structure, the language rule set including rules in both of the following categories (i) rules based on transitional probability of use of particular word sequences, and (ii) rules based on probability of relative positioning of words of particular word categories in a sentence structure; and PA0 (d) selecting, but use of the probability values derived in steps (b) and (c), one word from each word group for inclusion at a respective word position in a reconstructed sentence structure. PA0 (x) for each word position for which no word group including at least one word is identified in step (a) utilizing a stored word assembler to attempt to identify at least one of a suffix construction, a prefix construction and a combination word construction, and to thereby identify a word group including at least one word for the word position. PA0 (e) using the words selected in step (d) to provide a reconstruction of the entered sentence structure in at least one of the following forms: a viewable display, a printout, a synthesized voice output.